#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef int ElementType;
struct Node
{
    ElementType Data;
    struct Node* Next;
};
typedef struct Node* PtrToNode;
typedef PtrToNode List;

List CreateList()
{
    List L = NULL;
    return L;
}

List Insert_r(List L, ElementType X)
{
    if (L == NULL) {
        L = (List) malloc(sizeof(struct Node));
        L->Data = X;
        L->Next = NULL;
        return L;
    }
    
    PtrToNode s = (PtrToNode) malloc(sizeof(struct Node));
    s->Data = X;
    s->Next = NULL;
    PtrToNode p = L;
    while (p->Next != NULL) {
        p = p->Next;
    }
    p->Next = s;
    return L;
}

List Insert_f(List L, ElementType X)
{
    if (L == NULL) {
        L = (List) malloc(sizeof(struct Node));
        L->Data = X;
        L->Next = NULL;
        return L;
    }

    PtrToNode p = (PtrToNode) malloc(sizeof(struct Node));
    p->Data = X;
    p->Next = L;
    L = p;
    return L; 
}

bool Delete(List *L, int targetVal) // 必须用二级指针，因为要原地改变
{
    PtrToNode prev, p;
    prev = NULL; // 概念上在开始之前，首结点的prev结点也应该指向NULL
    for (p = *L; p && p->Data != targetVal; prev = p, p = p->Next)
        ;

    if (!p) // 没找到该结点
        return false;

    if (!prev) { // 删除的是第一个首结点
        *L = p->Next;
    } else {
        prev->Next = p->Next;
    }
    free(p);
    return true;
}


void Print_List(List L)
{
    PtrToNode p = L;
    while (p != NULL) {
        printf("%d ", p->Data);
        p = p->Next;
    }
}

int main()
{
    List L = CreateList();
    L = Insert_r(L, 1);
    L = Insert_r(L, 2);
    L = Insert_r(L, 3);
    L = Insert_r(L, 4);
    L = Insert_r(L, 5);
    // L = Insert_f(L, 1);
    // L = Insert_f(L, 2);
    // L = Insert_f(L, 3);
    // L = Insert_f(L, 4);
    // L = Insert_f(L, 5);
    Delete(&L, 1);
    Print_List(L);
    return 0;
}